import java.util.*;

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.buildTree(new int[]{9,3,15,20,7}, new int[]{9,15,7,20,3}));
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
    int headPostIndex;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        Map<Integer, Integer> value2index = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            value2index.put(inorder[i], i);
        }
        headPostIndex = postorder.length - 1;
        return build(0, postorder, 0, value2index);
    }

    TreeNode build(int inMinIndex, int[] postorder, int postMinIndex, Map<Integer, Integer> value2index) {
        if (headPostIndex < postMinIndex) {
            return null;
        }
        int headValue = postorder[headPostIndex];
        TreeNode head = new TreeNode(headValue);
        headPostIndex--;
        int leftLen = value2index.get(headValue) - inMinIndex;
        head.right = build(inMinIndex + leftLen + 1, postorder, postMinIndex + leftLen, value2index);
        head.left = build(inMinIndex, postorder, postMinIndex, value2index);
        return head;
    }
}

//迭代
class Solution1 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int inIndex = inorder.length - 1;
        int postIndex = postorder.length - 1;
        TreeNode root = new TreeNode(postorder[postIndex--]);
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (postIndex >= 0) {
            TreeNode parent = stack.peek();
            TreeNode cur = new TreeNode(postorder[postIndex]);
            if (parent.val != inorder[inIndex]) {
                parent.right = cur;
            } else {
                stack.pop();
                inIndex--;
                while (!stack.isEmpty() && stack.peek().val == inorder[inIndex]) {
                    parent = stack.pop();
                    inIndex--;
                }
                parent.left = cur;
            }
            stack.push(cur);
            postIndex--;
        }
        return root;
    }
}